package gaobo.stack;

import java.util.Arrays;
import java.util.Stack;

public class MyStack {

    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;

    public MyStack(){
        this.elem = new int[DEFAULT_SIZE];
    }

    //入栈
    public int push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        return val;
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }

    //出栈
    public int pop(){
        if (empty()){
            throw new MyEmptyException("栈为空");
        }
      /*int ret = elem[usedSize-1];
        usedSize--;
        return ret;*/
        return elem[--usedSize];
    }
    public boolean empty(){
        return usedSize == 0;
    }
    //出栈2
    public int peek(){
        if (empty()){
            throw new MyEmptyException("栈为空");
        }
      /*int ret = elem[usedSize-1];
        usedSize--;
        return ret;*/
        return elem[usedSize-1];
    }

    //中缀表达式 转 后缀表达式【逆波兰式】【力扣150】
    //实现原理使用栈，很麻烦一般出选择题
    //常规应用:实现简单计算器
    //写代码出题:
    //将后缀表达式进行计算，求结果？
    //例:求123*+45*6+7*+ 结果
    //计算原理：遇到数字入栈，遇到运算符出栈顶两个数（第一个是右操作数 第二个是左操作数）进行计算再放入栈

    public int evalRPN(String[] tokens){
        //1.遍历tokens数组 判断当中的字符串的类型
        Stack<Integer> stack = new Stack<>();

        for (String s:tokens) {
            if (!isOperations(s)){
                stack.push(Integer.parseInt(s));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (s){
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperations(String s){
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            return true;
        }
        return false;
    }

    //递归转化为循环(非递归)——>使用栈
    //1.递归的结束条件【起始条件】
    //2.递推公式
    //singlelist 的 display2 -> display3

    //有效括号【力扣20】
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //1.判断是不是左括号
            if (ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }
            else {
                if (stack.empty()){
                    //2.遇到了右括号，但是栈为空
                    return false;
                }
                char ch2 = stack.peek();
                //3.此时如果满足这里面的任何一个匹配逻辑，都是匹配的
                if (ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']' ||ch2 == '{' && ch == '}'){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        //4.当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成
        if (!stack.empty()){
            return false;
        }
        return true;
    }

    //出入栈次序匹配【牛客JZ31】
    public boolean isPopOrder(int [] pushA, int [] popA){
    //思路:定义i下标遍历PushA数组，直接入栈
    //入栈之后判断j下标是不是当前入栈元素
    //如果是就出栈 j++
    //如果不是 则继续i++即可
        Stack<Integer> stack = new Stack<>();
        int j = 0;//遍历popA数组
        //遍历pushA数组
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek().equals(popA[j])){
                stack.pop();
                j++;
            }
        }
    //栈空返回true 非空返回false
    return stack.empty();
    }

    //实现一个最小栈【力扣155】
    //题目:设计一个支出push，pop，top(peek) 操作，并能在常数时间内检索到最小元素的栈

    /*逻辑
    push
    1.普通栈当中一定要放的,最小栈当中放不放？ 取决于当前元素X有没有最小栈的栈顶元素小
    2.如果要存放的值为X，最小栈的栈顶元素时Y
       X<Y 放, X==Y 放且必须放, X>Y 不放
     */
    //代码-> MinStack


}
